package com.sx.sx1.lintcode.day717;

import org.apache.log4j.Priority;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class LC1223 {

    public class Solution {
        /**
         * @param s:
         * @return: return a string
         */
        public String frequencySort(String s) {
            Map<Integer,PriorityQueue<Character>> m = new HashMap<>();
            Map<Character,Integer> cnt = new HashMap<>();
            for (int i = 0; i <s.length() ; i++) {
                char c = s.charAt(i);
                if(!cnt.containsKey(c)){
                    cnt.put(c,0);
                }

                cnt.put(c,cnt.get(c)+1);
            }

            PriorityQueue<Integer> total = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer a, Integer b) {
                    return b-a;
                }
            });
            for(char c: cnt.keySet()){
                int times  = cnt.get(c);
                if(!m.containsKey(times)){
                    total.add(times);
                    m.put(times,new PriorityQueue<>());
                }

                m.get(times).add(c);
            }


            StringBuilder sb = new StringBuilder();
            while (!total.isEmpty()){
                int times = total.poll();
                PriorityQueue<Character> chrs  = m.get(times);
                while (!chrs.isEmpty()){
                    char ch = chrs.poll();
                    for (int i = 0; i < times; i++) {
                        sb.append(ch);
                    }
                }
            }

            return sb.toString();
        }

    }


}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1233 · 根据字符出现频率排序
算法
中等
通过率
64%

题目
题解16
笔记
讨论6
排名
记录
描述
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
如果字符出现的次数相同，则按照他们的字典序排序。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入:
"tree"

输出:
"eert"

解释:
'e' 出现两次 ， 'r' 和 't' 都只出现一次。
所以'e'必须排在'r'和't'之前，并且r的字典序更小。
样例 2:

输入:
"cccaaa"

输出:
"aaaccc"

解释:
'c' 和 'a'都出现了三次,所以答案是  "aaaccc" ，而不是 "cccaaa"
相关知识
学习《2024年7月北美大厂最新面试真题精讲》课程中的3.9Meta：最新面试精选005相关内容 ，了解更多相关知识！
标签
企业
Amazon
Google
相关题目

209
第一个只出现一次的字符
简单

1281
前K个高频元素
中等
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
17/46
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
